//给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR)
// 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。 
//
// 示例 1: 
//
// 输入: s = "1^0|0|1", result = 0
//
//输出: 2
//解释: 两种可能的括号方法是
//1^(0|(0|1))
//1^((0|0)|1)
// 
//
// 示例 2: 
//
// 输入: s = "0&0&0&1^1|0", result = 1
//
//输出: 10 
//
// 提示： 
//
// 
// 运算符的数量不超过 19 个 
// 
// Related Topics 记忆化搜索 字符串 动态规划 
// 👍 47 👎 0

package leetcode.editor.cn;

/**
 * Java：布尔运算
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P面试题_08_14_BooleanEvaluationLcci {
    public static void main(String[] args) {
        Solution solution = new P面试题_08_14_BooleanEvaluationLcci().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * @param str    待计算字符串
         * @param result 0-false 1-true
         */
        public int countEval(String str, int result) {
            if ((result != 0 && result != 1) || str == null || (str.length() & 1) == 0) {
                return 0;
            }
            int N = str.length();
            Info[][] dp = new Info[N][N];
            Info info = process(str.toCharArray(), 0, N - 1, dp);
            return result == 1 ? info.t : info.f;
        }

        /**
         * 递归返回的对象
         */
        public class Info {
            int t; // 计算结果为true的方法数
            int f; // 计算结果为false的方法数

            public Info(int t, int f) {
                this.t = t;
                this.f = f;
            }
        }

        /**
         * 递归含义：在str的L-R范围内计算出Info，L-R返回个数为奇数且LR非0即1
         */
        public Info process(char[] strs, int L, int R, Info[][] dp) {
            if (dp[L][R] != null) {
                return dp[L][R];
            }
            int t = 0;
            int f = 0;
            // L和R相同位置就只有一种情况了
            if (L == R) {
                t = strs[L] == '1' ? 1 : 0;
                f = strs[L] == '0' ? 1 : 0;
            }
            // L和R至少隔3个数，遍历每个逻辑运算符累加上结果
            else {
                for (int i = L + 1; i <= R - 1; i += 2) {
                    Info left = process(strs, L, i - 1, dp);
                    Info right = process(strs, i + 1, R, dp);
                    int lt = left.t;
                    int lf = left.f;
                    int rt = right.t;
                    int rf = right.f;
                    switch (strs[i]) {
                        case '&':
                            t += lt * rt; // 两边都必须是true
                            f += lt * rf + lf * rt + lf * rf; // 两边都必须不同时为true
                            break;
                        case '|':
                            t += lt * rt + lt * rf + lf * rt; // 两边都必须不同时为false
                            f += lf * rf; // 两边都必须同时为false
                            break;
                        case '^':
                            t += lt * rf + lf * rt; // 两边都必须不同
                            f += lt * rt + lf * rf; // 两边都必须相同
                            break;
                    }
                }
            }
            dp[L][R] = new Info(t, f);
            return dp[L][R];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}